﻿using System;
using System.Collections.Generic;
using System.Text;

namespace FirstBadVersion
{
    /* The isBadVersion API is defined in the parent class VersionControl.
          bool IsBadVersion(int version); */


    public class VersionControl
    {
        private int _badVersion = 2126753390;

        public bool IsBadVersion(long version)
        {
            return this._badVersion <= version;
        }
    }

    public class Solution : VersionControl
    {
        public int FirstBadVersion(int n)
        {
            // int mid = 0;
            // long first = 1;
            // long last = n;
            // while (last >= first)
            // {
            //     mid = (int) ((first + last) / 2);
            //     if (IsBadVersion(mid))
            //     {
            //         last = mid - 1;
            //     }
            //     else
            //     {
            //         first = mid + 1;
            //     }
            // }
            //
            // return mid;

            int first = 1;
            int last = n;
            int mid = 0;
            do
            {
                long n1 = first;
                long n2 = last;
                mid = (int) ((n1 + n2) / 2);

                if (IsBadVersion(mid) && IsBadVersion(mid - 1))
                {
                    last = mid - 1;
                }
                else
                {
                    first = mid + 1;
                }

                if (IsBadVersion(mid) ^ IsBadVersion(mid - 1))
                {
                    break;
                }
                else if (IsBadVersion(mid) ^ IsBadVersion(mid + 1))
                {
                    mid++;
                    break;
                }
            } while (true);

            return mid;
        }
    }
}